// 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
// 此外，你可以假设该网格的四条边均被水包围。

// 暴露接口
function numIslands(grid: string[][]): number {
    // 安全检测
    if (grid.length < 1) {
        return 0;
    }
    let count: number = 0;// 计数变量
    const queue: number[][] = [];// 队列
    let directions: number[][] = [[1, 0], [0, 1], [-1, 0], [0, -1]];// 方向变量
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === "1") {// 对矩阵中每个格子尝试使用BFS
                count++;// 发现新岛屿时计数变量+1
                queue.push([i, j]);// 将当前元素的坐标入队
                grid[i][j] = "2";// 把矩阵标记为“2”，表示为访问过
                BFS(grid, queue, directions);
            }
        }
    }
    return count;
};


// 广度优先遍历函数
function BFS(grid: string[][], queue: number[][], directions: number[][]) {
    // 使用队列来实现广度优先遍历
    while (queue.length > 0) {
        let currPos: number[] = queue.shift() as number[];
        let posX: number = currPos[0];// 当前出队元素X
        let posY: number = currPos[1];// 当前出堆元素Y
        // 注意：如何使用方向变量对矩阵进行遍历
        for (let direction of directions) {
            let new_posX: number = posX + direction[0];// 计算出随方向变量移动的元素X坐标
            let new_posY: number = posY + direction[1];// 计算出随方向变量移动的元素Y坐标
            if (new_posX >= 0 && new_posX < grid.length &&
                new_posY >= 0 && new_posY < grid[0].length &&
                grid[new_posX][new_posY] === "1") {
                    // 入队的条件：1、边界不溢出 
                    // 2、这个元素之前没有被访问过，不然会造成重复入队
                queue.push([new_posX, new_posY]);
                grid[new_posX][new_posY] = "2";
            }
        }
    }
}

// 留意一下我这里对矩阵元素周围的四个方向遍历没有采用常规的if堆叠的方式遍历，
// 而是采用了一个方向变量“directions”，直接对方向变量遍历就可以得到结果坐标...比使用if嵌套要简洁的多
